#include "max_subarray.h"
#include "random_number_generator.h"
#include <gtest/gtest.h>

using namespace std;

class MaxSubArrayTest : public testing::Test
{
public:
    void SetUp()
    {
    }

    void TearDown()
    {
    }
};


TEST_F(MaxSubArrayTest, test)
{
    int* array = NULL;
    size_t len = 10;
    RandomNumberGenerator::Generate(array, len, -20, 20);

    for ( size_t i = 0; i < len; ++i )
    {
        cout << "array[" << i << "] = " << array[i] << endl;
    }
    cout << endl;

    size_t max_begin;
    size_t max_end;
    int max_sum;

    max_subarray(array, 0, len, max_begin, max_end, max_sum);
    cout << "max_begin is " << max_begin << endl;
    cout << "max_end is " << max_end << endl;
    cout << "max_sum is " << max_sum << endl;

    cout << endl;

    size_t max_begin_bf = 0;
    size_t max_end_bf = 0;
    int max_sum_bf = numeric_limits<int>::min();
    for ( size_t i = 0; i < len; ++i )
    {
        for ( size_t j = i + 1; j <= len; ++j )
        {
            int current_max_sum = 0;
            for ( size_t k = i; k < j; ++k )
            {
                current_max_sum += array[k];
            }
            if ( current_max_sum > max_sum_bf )
            {
                max_begin_bf = i;
                max_end_bf = j;
                max_sum_bf = current_max_sum;
            }
        }
    }

    cout << "max_begin_bf is " << max_begin_bf << endl;
    cout << "max_end_bf is " << max_end_bf << endl;
    cout << "max_sum_bf is " << max_sum_bf << endl;

    cout << endl;

    ASSERT_EQ(max_begin_bf, max_begin);
    ASSERT_EQ(max_end_bf, max_end);
    ASSERT_EQ(max_sum_bf, max_sum);

}
